package LeetCode.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 组合总和
 * @author: leiwenkang02@meituan.com
 * @date: 2019/1/3
 * @time: 19:24
 */
public class Test39组合总数 {
    public static void main(String[] args) {
        Test39组合总数 test = new Test39组合总数();
        int[] candidates = {2, 3, 5};
        List<List<Integer>> result = test.combinationSum(candidates, 8);
        System.out.println(result);

    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        getResult(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    /**
     *思路 https://blog.csdn.net/jaster_wisdom/article/details/80683651
     * 固定第一个元素2以后，再从数组所有元素中找和为tagert-2的所有组合
     * 递归到子集合的条件是target < 0,该子集合不合适；target == 0,该子集合满足条件
     * 无论子集合是否符合，均需要回溯，回退一格，从剩余元素中再找
     * 比如找到2-2-2-2，回退2-2-2，找到2-2-2-3发现不能进入循环，终止，返回上一次2-2-2的调用，继续remove，剩余2-2
     * 再继续加3，2-2-3，再加入2失败，remove。。。
     */
    private void getResult(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start){
        if (target < 0) {
            return;
        } else if (target == 0 ){
            result.add(new ArrayList<Integer>(cur));
        } else if (target > 0){
            for (int i = start; i < candidates.length && target >= candidates[i]; i++){
                cur.add(candidates[i]);
                getResult(result, cur, candidates, target - candidates[i], i);
                cur.remove(cur.size() - 1);
            }
        }

    }


}
